using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStructure
{
    public class Array2<T>
    {
        private T[] data; //存储元素
        private int first;//记录头部
        private int last;//记录尾部
        private int size;//当前元素个数
        
        public Array2(int capacity)
        {
            data = new T[capacity];
            
            first = 0;
            last = 0;
            size = 0;
        }
        public Array2() : this(10) { }
        
        public int Count => size;
        public bool IsEmpty => size == 0;
        
        //添加元素
        public void AddLast(T newData)
        {
            if (size == data.Length)
                ResetCapacity(2 * data.Length);
                
            data[last] = newData;
            last = (last+1)%data.Length;
            size++;
        }
        //删除元素
        public T RemoveFirst()
        {
            if (IsEmpty)
                throw new Exception("数组为空");
                
            T res = data[first];
            data[first] = default(T);
            
            first = (first + 1) % data.Length;
            size--;
            
            if (size == data.Length / 4)
                ResetCapacity(data.Length / 2);
                
            return res;
        }
        //获取元素
        public T GetFirst()
        {
            if (IsEmpty)
                throw new Exception("数组为空");

            return data[first];
        }
        
        private void ResetCapacity(int newCapacity)
        {
            T[] newData = new T[newCapacity];
            
            for (int i = 0; i < size; i++)
                newData[i] = data[(first + i) % data.Length];
                
            data = newData;
            first = 0;
            last = size;
        }
        public override string ToString()
        {
            StringBuilder res = new StringBuilder();
            res.Append("[");
            for(int i = 0; i < size; i++)
            {
                res.Append(data[(first + i) % data.Length]);
                if((first + i + 1) % data.Length != last)
                    res.Append(", ");
            }
            res.Append("]");
            return res.ToString();
        }
    }
}